#include "main/utils.h"
using namespace std;

class KthLargest {
  public:
    KthLargest(int k, vector<int> vec) : k_(k), cur_nums_(vec) {
      make_heap(cur_nums_.begin(), cur_nums_.end(), greater<int>());
      while (cur_nums_.size() > k) {
        pop_heap(cur_nums_.begin(), cur_nums_.end(), greater<int>());
        cur_nums_.pop_back();
      }
    }

    int add(int num) {
      if (cur_nums_.size() < k_) {
        cur_nums_.push_back(num);
        push_heap(cur_nums_.begin(), cur_nums_.end(), greater<int>());
        return cur_nums_.front();
      }
      if (cur_nums_.front() < num) {
        cur_nums_.push_back(num);
        pop_heap(cur_nums_.begin(), cur_nums_.end(), greater<int>());
        cur_nums_.pop_back();
      }
      return cur_nums_.front();
    }

  private:
    int k_;
    vector<int> cur_nums_;
};

int main() {
  vector<int> vec = {4, 5};
  KthLargest kthLargest(3, vec);
  cout << kthLargest.add(8) << endl;
  cout << kthLargest.add(2) << endl;
  cout << kthLargest.add(3) << endl;
  cout << kthLargest.add(5) << endl;

  return 0;
}
